package com.example.demo.shuatiban.zuocheng;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author xujm
 * @version V2.4
 *
 *  一个数组 arr中，
 *  两个数的差为非负整数K，使用过的数不能再用，问有多少个组合?
 *
 *  方法1: 暴力
 *
 *  方法2: 贪心 定义 L,R 两个下标 往右移动 寻找组合
 *   注意L 不能超过 R，使用过的无法再用
 *
 * @since 2.4.0 2022/3/20 15:37
 */
public class Arr_两个数组合差为K的组成一对 {


    //暴力
    // 先全排列，然后针对所有的排列 01,23,45 依次比对，找出组合数最多的返回
    public static int baoli(int [] arr, int k){

        List<List<Integer>> res = new ArrayList<>();
        digui(arr,new boolean[arr.length],0,new ArrayList<>(),res);


        int lastResult = 0;
        for(List<Integer> tempList : res){
            int result = 0;
            for(int i=0;i< tempList.size()-1;i=i+2){
                if(tempList.get(i+1) - tempList.get(i) == k){
                    result++;
                }
            }
            lastResult = Math.max(lastResult,result);
        }
        return lastResult;
    }


    public static void digui(int [] arr, boolean [] flag, int index,List<Integer> tempList, List<List<Integer>> resList){

        if(index == arr.length){
            resList.add(new ArrayList<>(tempList));
            return;
        }
        for(int i=0;i<arr.length;i++){
            if(flag[i]){
                continue;
            }
            flag[i] = true;
            tempList.add(arr[i]);
            digui(arr,flag,index+1,tempList,resList);
            tempList.remove(tempList.size()-1);
            flag[i] = false;
        }

    }


    // 贪心
    public static int complete(int [] arr, int k){

        Arrays.sort(arr);
        boolean [] flag = new boolean[arr.length];
        int L=0,R=1;
        int res = 0;
        while(L < arr.length && R < arr.length){

            if(L>=R){
                R++;
                continue;
            }
            if(flag[L]){
                L++;
                continue;
            }
            if (flag[R]){
                R++;
                continue;
            }

            if(arr[R] - arr[L] == k){
                flag[L]=true;
                flag[R]=true;
                L++;
                R++;
                res++;
                continue;
            }

            if(arr[R] - arr[L] < k){
                R++;
                continue;
            }

            if(arr[R] - arr[L] > k){
                L++;
                continue;
            }
        }
        return res;
    }

    public static void main(String[] args) {

        int [] arr = {1,3,7};
        System.out.println(baoli(arr,2));
        System.out.println(complete(arr,2));

    }

}
